package leetcode;

import java.util.Stack;

/**
 * 61.旋转链表
 * <p>
 * 给定一个链表，旋转链表，将链表每个节点向右移动 k 个位置，其中 k 是非负数。
 * <p>
 * 示例 1:
 * <p>
 * 输入: 1->2->3->4->5->NULL, k = 2
 * 输出: 4->5->1->2->3->NULL
 * 解释:
 * 向右旋转 1 步: 5->1->2->3->4->NULL
 * 向右旋转 2 步: 4->5->1->2->3->NULL
 * 示例 2:
 * <p>
 * 输入: 0->1->2->NULL, k = 4
 * 输出: 2->0->1->NULL
 * 解释:
 * 向右旋转 1 步: 2->0->1->NULL
 * 向右旋转 2 步: 1->2->0->NULL
 * 向右旋转 3 步: 0->1->2->NULL
 * 向右旋转 4 步: 2->0->1->NULL
 * <p>
 * <p>
 *
 *
 * 1，如果k大于n，只移动k%n和移动k结果是一样的
 * 2，从原链表后边找到第k+1个节点，他的下一个节点就是新链表的头结点
 */
public class RotateRight {
    public ListNode rotateRight(ListNode head, int k) {


        if (k == 0 || head == null || head.next == null) {
            return head;
        }

        int length = 1;
        ListNode tail = head;
        Stack<ListNode> stack = new Stack();
        stack.push(head);
        while (tail.next != null) {
            tail = tail.next;
            stack.push(tail);
            length++;
        }
        if (k % length == 0) {
            return head;
        }

        // 做成环
        tail.next = head;

        ListNode pre = null;
        for (int i = 0; i < k % length + 1; i++) {
            pre = stack.pop();
        }
        ListNode result = pre.next;
        pre.next = null;

        return result;

    }

    public class ListNode {
        int val;
        ListNode next;

        ListNode(int x) {
            val = x;
        }
    }
}
